It is known that in modern data processing systems the speed at which a processor may operate on information is much greater than the speed at which information can be provided to the processor by a working memory.
Among the arrangements most commonly used to overcome this problem, there is the use of buffer memories or caches having a small capacity but operating at very high speed. They are used to temporarily store those portions of the main memory contents which are likely to be needed by the processor for immediate use.
Basically a cache may be considered an associative memory having a plurality of memory locations: in each location a copy of a datum stored in working memory is contained, as well as the corresponding main memory address where the datum is stored.
When the cache receives a memory address, it is compared with all the addresses contained in the cache and, if a match occurs, the information related to the address for which match occurs is output.
In practice, this association is obtained by dividing a memory address in two parts, a more significant one and a least significant.
The least significant part is used to address a high speed memory which, at each addressed location, contains a datum and the most significant portion of the datum's address.
The most significant part of the effective address, read out from the high speed memory, is compared with the most significant portion of the main memory address. If they match, the data information read out from the cache is validated by a HIT signal to indicate that it is effectively the information related to the full referencing address.
In a data processing system which makes use of the "virtual memory" concept, the addresses generated by a processor to reference the working memory are logical or virtual addresses and differ from the physical addresses which are effectively used to reference the working memory.
Virtual or logical addresses, before being forwarded to the working memory, must be "translated" into physical addresses by a memory management unit or MMU.
The MMU, in turn, may be considered a cache of addresses.
Thus, two alternatives are available to fast memories commonly defined as caches (data caches as opposed to memory management units). They may be referenced by either a physical or a logical address.
Both alternatives have been used and each one has its own advantages and trade-offs.
Addressing of a cache with a physical address requires the previous translation of the logical address into a physical address: the time required to get the referenced information from the cache is the sum of the address translation time performed by the MMU and the cache memory access time.
In several applications this delay is unacceptable.
In the other alternative, addressing of a cache by logical addresses, the time required to get the referenced information from the cache is only the access time of the cache.
However this approach requires an unambiguous relation between a logical address and a physical address.
At logical address level, synonyms must not exist.
Should this occur the same information could be duplicated in several cache locations and could cause information inconsistencies which must be avoided.
These problems, which find solution by way of expensive expedients or with heavy limitations at programming level, discourage the use of logical addresses for cache references.
An alternative to the two approaches flows from the fact that in general logical addresses and physical addresses are not completely different but contain a bit field, the least significant one, which is named "offset" and coincides in both the logical and physical address.
It is therefore possible to address a cache with the "offset" field only, which however limits the cache capacity to the only range of locations which may be addressed with the "offset" (generally 1K of addressable locations).
Unfortunately, to obtain good performances from a cache it is required to have cahes with a much greater capacity in the order of 4-16K addressable locations.
The European patent application published with N. 206050 on 30.12.86, which is also referenced for a more detailed consideration of the problems involved in cache memories, proposes an alternative solution of the above mentioned problems, and provides for the addressing of a cache by means of a logical or virtual address, or more properly a portion thereof, and the simultaneous addressing of a memory management unit or "Translation Buffer", with the same logical address to obtain the corresponding physical address.
The cache memory outputs, in addition to the requested information (if present) the physical address related to that information (obviously excluding the "offset" field), so that, if the retrieved physical address matches with the physical address generated by the "Translation Buffer", there is the confirmation, or HIT, that the retrieved information is the requested one.
In this way, the Translation Buffer and the cache memory work in parallel or overlapping in time.
It is therefore clear that the time required to obtain a datum is determined by the greater of the access time of the Translation Buffer and the access time of the cache memory, plus the time required to compare the addresses in output from the two elements.
In general, the translation time of a logical address into a physical address is no less than the cache access time. Therefore the speed at which a cache may provide valid information may be limited with this approach by the operative time of the Translation Buffer.
Moreover, the problem of synonyms in the logical addresses, even if reduced, is not completely overcome; it must be avoided that logical addresses, differing in that portion which is used to address the cache, may reference the same information.
These limitations are completely overcome by the cache memory of the present invention, which may be defined as having a pseudo virtual addressing.